package com.xiaolin.algorithm.recursion;

import java.util.LinkedList;

/**
 * @ClassName Solution
 * @Description 斐波那契数列
 * @Detail detail
 * @Author MyPC
 * @Date 2020/12/27
 * @Version 1.0
 */
class Solution {
    public static void main(String[] args) {
        long fib = fib(45);
        System.out.println(fib);
        StringBuilder sb=new StringBuilder("[");
        sb.replace(sb.length()-1,sb.length(),"");
        System.out.println(sb);
        System.out.println(numWays(45));
        System.out.println(myPow(2.00000,
                -2147483648));
        ListNode head=new ListNode(1);
        head.next=new ListNode(2);
        head.next.next=new ListNode(3);
        ListNode listNode = reverseList(head);
        System.out.println(listNode.next.next.val);
        char a='a';
        System.out.println((int)a);
    }
    public static long fib(long n) {
        if(n==0){
            return 0;
        }
        if(n==1){
            return 1;
        }
        long first=0;
        long second=1;
        long third=0;
        for(int i=2;i<=n;i++){
            third=first+second;
            first=second;
            second=third;
        }
        return third;
    }

    public static int numWays(int n) {
        if(n==0){
            return 1;
        }
        if(n==1){
            return 1;
        }
        int first=0;
        int second=1;
        for(int i=2;i<=n;i++){
            second=first+second;
            first=second-first;
        }
        return (int)(second%(1e9+7));

    }

    public static double myPow(double x, int n) {
        if(n==0){
            return 1;
        }
        double result=x;
        int an=Math.abs(n);
        if(an<0){
            return 0;
        }
        int count = an / 2 - 1;
        for(int i=0;i<count;i++){
            result*=x;
        }
        if(an/2 >0){
            result*=result;
        }
        if(an>1 && n%2!=0){
            result=result*x;
        }
        if(n<0){
            result=1/result;
        }
        return result;
    }

    public static ListNode reverseList(ListNode head) {
        LinkedList<ListNode> linkedList=new LinkedList<>();
        while(head!=null){
            linkedList.push(head);
            head=head.next;
        }
        ListNode newNode=null;
        if(linkedList.peekFirst()!=null){
            newNode=linkedList.pollFirst();
        }
        ListNode temp=newNode;
        while(linkedList.peekFirst()!=null){
            temp.next=linkedList.pollFirst();
            temp=temp.next;
            temp.next=null;
        }
        return newNode;
    }

     static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
     }

}